{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 二叉树\n",
    "\n",
    "```\n",
    "    3\n",
    "   / \\\n",
    "  9  20\n",
    "    /  \\\n",
    "   15   7\n",
    "   \n",
    "先序遍历：3 9 20 15 7\n",
    "中序遍历：9 3 15 20 7\n",
    "后序遍历：9 15 7 20 3\n",
    "```\n",
    "\n",
    "二叉树定义\n",
    "\n",
    "```java\n",
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * public class TreeNode {\n",
    " *     int val;\n",
    " *     TreeNode left;\n",
    " *     TreeNode right;\n",
    " *     TreeNode(int x) { val = x; }\n",
    " * }\n",
    " */\n",
    "```\n",
    "\n",
    "二叉树的遍历\n",
    "\n",
    "1. 先序遍历\n",
    "\n",
    "(1), 遍历根结点\n",
    "\n",
    "(2), 先序遍历左子树\n",
    "\n",
    "(3), 先序遍历右子树\n",
    "\n",
    "```java\n",
    "class Solution {\n",
    "    public List<Integer> preorderTraversal(TreeNode root) {\n",
    "        if (root != null) {\n",
    "            System.out.println(root.val);\n",
    "            preorderTraversal(root.left);\n",
    "            preorderTraversal(root.right);\n",
    "        }\n",
    "    }\n",
    "}\n",
    "```\n",
    "\n",
    "2. 中序遍历\n",
    "\n",
    "- 1, 中序遍历左子树\n",
    "- 2, 遍历根结点\n",
    "- 3, 中序遍历右子树\n",
    "\n",
    "```java\n",
    "class Solution {\n",
    "    public List<Integer> inorderTraversal(TreeNode root) {\n",
    "        if (root != null) {\n",
    "            inorderTraversal(root.left);\n",
    "            System.out.println(root.val);\n",
    "            inorderTraversal(root.right);\n",
    "        }\n",
    "    }\n",
    "}\n",
    "```\n",
    "\n",
    "3. 后序遍历\n",
    "\n",
    "- 1, 后序遍历左子树\n",
    "- 2, 后序遍历右子树\n",
    "- 3, 遍历根结点\n",
    "\n",
    "```java\n",
    "class Solution {\n",
    "    public List<Integer> postorderTraversal(TreeNode root) {\n",
    "        if (root != null) {\n",
    "            postorderTraversal(root.left);\n",
    "            postorderTraversal(root.right);\n",
    "            System.out.println(root.val);\n",
    "        }\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 二叉搜索树定义：\n",
    "\n",
    "1. 左子树也是一颗二叉搜索树\n",
    "2. 右子树也是一颗二叉搜索树\n",
    "3. 左子树 < 根结点 < 右子树\n",
    "\n",
    "```\n",
    "def find(root, target):\n",
    "    if root == Null:\n",
    "        return False\n",
    "    if target > root.val:\n",
    "        return find(root.right, target)\n",
    "    else if target < root.val:\n",
    "        return find(root.left, target)\n",
    "    else:\n",
    "        return True\n",
    "```\n",
    "\n",
    "如果是平衡二叉搜索树，find的时间复杂度为O(logN)\n",
    "\n",
    "最坏情况，二叉搜索树会退化成链表\n",
    "\n",
    "```\n",
    "1\n",
    " \\\n",
    "  2\n",
    "   \\\n",
    "    3\n",
    "     \\\n",
    "      4\n",
    "```\n",
    "\n",
    "二叉搜索树如何变平衡呢？\n",
    "\n",
    "```\n",
    "1\n",
    " \\\n",
    "  2\n",
    "   \\\n",
    "    3\n",
    "```\n",
    "\n",
    "变成\n",
    "\n",
    "```\n",
    "   2\n",
    "  / \\\n",
    " 1   3\n",
    "```\n",
    "\n",
    "平衡二叉树的定义：\n",
    "\n",
    "左子树的高度和右子树的高度相差不超过1，且左子树和右子树都是二叉搜索树\n",
    "\n",
    "```\n",
    "def checkBalance(root):\n",
    "    if root == None:\n",
    "        return True\n",
    "    if checkBalance(root.left) == False:\n",
    "        return False\n",
    "    if checkBalance(root.right) == False:\n",
    "        return False\n",
    "    return abs(treeHeight(root.left) - treeHeight(root.right)) <= 1\n",
    "    \n",
    "def treeHeight(root):\n",
    "    if root == None:\n",
    "        return 0\n",
    "    leftTreeHeight = treeHeight(root.left)\n",
    "    rightTreeHeight = treeHeight(root.right)\n",
    "    return max(leftTreeHeight, rightTreeHeight) + 1\n",
    "```\n",
    "\n",
    "最著名的平衡二叉树：AVL树和红黑树\n",
    "\n",
    "不管插入节点还是删除节点的时候，都需要对树进行旋转操作，使树保持平衡状态。\n",
    "\n",
    "\n",
    "针对字段建索引的过程就是将乱序数据排序的过程，或者说是生成一颗类似于平衡二叉搜索树的过程。将搜索时间复杂度由O(N) -> O(logN)\n",
    "\n",
    "为什么不对所有字段建索引\n",
    "\n",
    "因为建索引会将插入数据的时间复杂度由O(1) -> O(logN)\n",
    "\n",
    "\n",
    "索引使用的平衡树一般是B树、B+树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
